package com.godme.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {7, 6, 4, 3, 5, 2, 10, 9, 8};
        System.out.println("排序前：" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    public static void heapSort(int[] arr){
        for(int index=arr.length-1;index>=0;index--){
            election(arr, 0, index);
            change(arr, 0, index);
        }
    }

    public static void election(int[] arr, int parentIndex, int boundary){
        if(arr.length < 2){
            return;
        }
        if(parentIndex > boundary){
            return;
        }
        int leftIndex = leftChildIndex(parentIndex);
        if(leftIndex > boundary){
            return;
        }
        int rightIndex = leftIndex + 1;

        election(arr, leftIndex, boundary);
        election(arr, rightIndex, boundary);
        int maxIndex = leftIndex;
        if(rightIndex <= boundary && arr[rightIndex] > arr[leftIndex]){
            maxIndex = rightIndex;
        }
        if(arr[parentIndex] < arr[maxIndex]){
            change(arr, parentIndex, maxIndex);
        }
    }

    public static void change(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    public static int leftChildIndex(int prentIndex){
        return 2*prentIndex + 1;
    }

    public static int rightChildIndex(int parentIndex){
        return leftChildIndex(parentIndex) + 1;
    }
}